package com.yt.ds.chapter4;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author: lzf
 * @Date: 2020/7/28 16:20
 * @Description: 广度优先搜索路径
 */
public class BreadthFirstPaths implements Paths {
    private boolean[] marked;
    private int[] edgeTo;
    private final int s;        // 起点

    public BreadthFirstPaths(Graph graph, int s) {
        marked = new boolean[graph.getVertexNum()];
        edgeTo = new int[graph.getVertexNum()];
        this.s = s;
        bfs(graph, s);
    }

    /**
     * 描述：广度优先搜索路径
     *
     * @param graph 图
     * @param s     起点
     * @return "void"
     * @date: 2020/7/28 16:30
     */
    private void bfs(Graph graph, int s) {
        Queue<Integer> queue = new LinkedList<>();
        marked[s] = true;
        queue.offer(s);
        while (!queue.isEmpty()) {
            int v = queue.poll();
            for (int x : graph.adj(v)) {
                if (!marked[x]) {
                    edgeTo[x] = v;
                    marked[x] = true;
                    queue.offer(x);
                }
            }
        }
    }

    @Override
    public boolean hasPathTo(int v) {
        return marked[v];
    }

    @Override
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) {
            return null;
        }
        Stack<Integer> path = new Stack<>();
        for (int x = v; x != s; x = edgeTo[x]) {
            path.push(x);
        }
        path.push(s);
        return path;
    }
}
